package bytedance;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

public class Meituan {


//    private int backtrcing(int begin,int end, int[] books, int[] bookstores) {
//        for
//    }
    public int shouge(int m,int max,int[] ground,int[] edge){
        return dfs(ground,edge,max,0,0);
    }
    private int dfs(int[] ground, int[] edge, int max,int cur,int cur_count){
        int cur_groud = ground[cur];
        cur_count=cur_count+cur_groud;
        if(cur_count>max){
            return 0;
        }
        if(cur==ground.length-1) {
            if (cur_count <= max) {
                return 1;
            } else {
                return 0;
            }
        }
        int result = 0;
        int count = 0;
        for (int i = 0; i < edge.length; i++) {
            if(edge[i]==cur+1){
                count++;
                result+=dfs(ground,edge,max,i+1,cur_count);
            }
        }
        if(count==0){
            return 1;
        }
        return result;
    }

    public int wenjianliu(String n,String m){
        Map<Character, TreeSet<Integer>> map = new HashMap<>();
        for (int i = 0; i < n.length(); i++) {
            TreeSet<Integer> set  = map.getOrDefault(n.charAt(i),new TreeSet<>());
            set.add(i);
            map.put(n.charAt(i),set);
        }
        int result = 0;
        int cur = -1;
        for (int i = 0; i < m.length(); i++) {
            char purpose = m.charAt(i);
            TreeSet<Integer> set = map.get(purpose);
            if(set==null||set.size()==0){
                return -1;
            }
            Integer ceiling = set.ceiling(cur);
            if(ceiling!=null){
                result = result+(ceiling-cur-1);
                cur=ceiling;
            }else {
                Integer first = set.first();
                result = result+(first+n.length()-cur-1);
                cur = first;
            }
        }
        return result;
    }


    public int gecaoji(int m,int n,int k,int[][] array){
        int[][] grass = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                grass[i][j] = 1;
            }
        }
        for (int i = 0; i < k; i++) {
            int x = array[i][0];
            int y = array[i][1];
            int r = array[i][2];
            for (int j = 0; j < m; j++) {
                for (int l = 0; l < n; l++) {
                    if((j-x+1)*(j-x+1)+(l-y+1)*(l-y+1)<=r*r){
                        grass[j][l] = 0;
                    }
                }
            }
            if(i!=k-1){
                for (int j = 0; j < m; j++) {
                    for (int l = 0; l < n; l++) {
                        grass[j][l] = grass[j][l]+1;
                    }
                }
            }
        }
        int result = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                result = result+grass[i][j];
            }
        }
        return result;
    }
}
